#!/usr/bin/python
# -*- coding: utf8 -*-

import sys
import os
import shelve

from common import *
from rule import *

# a node means A(i, j), whese A is a non-terminal symbol
# we do not use class, because tuple is easy to used as key for set() and dict()
def Node(symbol, i, j):
    return (symbol, i, j)

def node_symbol(node):
    return get_symbol(node[0])

def node_s(node):
    return node[0]

def node_l(node):
    return node[1]

def node_r(node):
    return node[2]

def node_len(node):
    return node_r(node) - node_l(node) + 1

def node_string(node):
    return '%s[%d,%d]' % (get_symbol(node[0]).string(), node[1], node[2])

class Grammar:
    def do_cky(self, types):
        cky = {} # one big tables for cky, avoid to use huge amounts of tiny tables
        n = len(types)
        
        # cky init
        for i in range(0, n):
                for r in get_terminal_rules_by_rhs(types[i]):
                    node = Node(r.s, i, i)
                    cky[node] = None
        
        # cky main
        for l in range(2, n + 1):
            for i in range(0, n - l + 1):
                for m in range(0, l):
                    j = i + l - 1
                    k = i + m
                    for r in get_rules():
                        s_node = Node(r.s, i, j)
                        x_node = Node(r.x, i, k)
                        y_node = Node(r.y, k + 1, j)
                        if x_node in cky and y_node in cky:
                            if s_node not in cky:
                                cky[s_node] = []
                            cky[s_node].append((x_node, y_node, r.index))
        return cky


    def parse_sentence(self, sentence):
        self.types = sentence.types
        self.words = sentence.words
        cky = self.do_cky(sentence.types)

        start_node = Node(get_symbol('START').index, 0, len(sentence.types) - 1)
        self.nodes = [start_node]
        self.links = []
        lookup = {}
        lookup[start_node] = 0
        for node in self.nodes:
            s = lookup[node]
            
            def resovle_ref(ref):
                if ref not in lookup:
                    number = len(self.nodes)
                    self.nodes.append(ref)
                    lookup[ref] = number
                else:
                    number = lookup[ref]
                return number

            paths = cky[node]
            if paths == None:
                continue
            for path in paths:
                x = resovle_ref(path[0])
                y = resovle_ref(path[1])
                r = path[2]
                self.links.append((s, x, y, r))
        self.links.sort(key = lambda link: node_len(self.nodes[link[0]]))

        cky.clear()
        lookup.clear()


    def log(self, file):
        for node in self.nodes:
            file.write('N %s\n' % node_string(node))
        for link in self.links:
            file.write('L %s->%s%s\n' % tuple(node_string(self.nodes[n]) for n in link[0:3]))
        file.write('E\n')


    def store(self, file):
        for node in self.nodes:
            file.write('N %s\n' % node_string(node))
        for link in self.links:
            file.write('L %s\n' % link_string(link))
        file.write('E\n')


    def load(self, file):
        self.nodes = []
        self.links = []

        while True:
            line = file.readline()
            if line == '':
                return False
            cells = line.split()

            if cells[0] == 'E':
                return True
            elif cells[0] == 'N':
                self.nodes.append(parse_node(cells[1]))
            elif cells[0] == 'L':
                nodes = [parse_node(cell) for cell in cells[1:]]
                i = node_left(nodes[0])
                j = node_right(nodes[0])
                k = node_right(nodes[1])
                rule = get_rule(node_symbol(nodes[0]),
                                (node_symbol(nodes[1]), node_symbol(nodes[2])))
                self.links.append(pack_link(i, j, k, rule))
            else:
                return True
